package main

func closedIsland(grid [][]int) int {
	if len(grid) == 0 {
		return 0
	}
	m := len(grid)
	n := len(grid[0])
	for i := 0; i < m; i++ {
		if grid[i][0] == 0 {
			bfs(grid, i, 0)
		}
		if grid[i][n-1] == 0 {
			bfs(grid, i, n-1)
		}
	}
	for j := 0; j < n; j++ {
		if grid[0][j] == 0 {
			bfs(grid, 0, j)
		}
		if grid[m-1][j] == 0 {
			bfs(grid, m-1, j)
		}
	}
	result := 0
	for i, row := range grid {
		for j, v := range row {
			if v == 0 {
				result++
				bfs(grid, i, j)
			}
		}
	}
	return result
}

func bfs(grid [][]int, i, j int) {
	if i < 0 || j < 0 || i == len(grid) || j == len(grid[0]) {
		return
	}
	if grid[i][j] == 1 {
		return
	}
	grid[i][j] = 1
	bfs(grid, i-1, j)
	bfs(grid, i+1, j)
	bfs(grid, i, j-1)
	bfs(grid, i, j+1)
}

func printGrid(grid [][]int) {
	for _, row := range grid {
		for _, v := range row {
			print(v, " ")
		}
		print("\n")
	}
}

func main() {
	grid := [][]int{
		{0, 0, 1, 1, 0, 1, 0, 0, 1, 0},
		{1, 1, 0, 1, 1, 0, 1, 1, 1, 0},
		{1, 0, 1, 1, 1, 0, 0, 1, 1, 0},
		{0, 1, 1, 0, 0, 0, 0, 1, 0, 1},
		{0, 0, 0, 0, 0, 0, 1, 1, 1, 0},
		{0, 1, 0, 1, 0, 1, 0, 1, 1, 1},
		{1, 0, 1, 0, 1, 1, 0, 0, 0, 1},
		{1, 1, 1, 1, 1, 1, 0, 0, 0, 0},
		{1, 1, 1, 0, 0, 1, 0, 1, 0, 1},
		{1, 1, 1, 0, 1, 1, 0, 1, 1, 0},
	}
	println(closedIsland(grid))
}
